<!DOCTYPE html>













<html class="theme-next gemini" lang="zh-CN">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2"/>
<meta name="theme-color" content="#222">












<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=6.4.2" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=6.4.2">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32.ico?v=6.4.2">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16.ico?v=6.4.2">


  <link rel="mask-icon" href="/images/logo.svg?v=6.4.2" color="#222">









<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '6.4.2',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    fastclick: false,
    lazyload: false,
    tabs: true,
    motion: {"enable":false,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>


  





  <meta name="description" content="正睿OI时间/空间限制均为1s/512MB 绿">
<meta name="keywords" content="题解,ZROI">
<meta property="og:type" content="article">
<meta property="og:title" content="ZROI-week11">
<meta property="og:url" content="https://sshwy.gitee.io/2018/10/01/51581/index.html">
<meta property="og:site_name" content="Sailor&#39;s Blog">
<meta property="og:description" content="正睿OI时间/空间限制均为1s/512MB 绿">
<meta property="og:locale" content="zh-CN">
<meta property="og:updated_time" content="2018-11-17T15:41:31.890Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="ZROI-week11">
<meta name="twitter:description" content="正睿OI时间/空间限制均为1s/512MB 绿">






  <link rel="canonical" href="https://sshwy.gitee.io/2018/10/01/51581/"/>



<script type="text/javascript" id="page.configurations">
  CONFIG.page = {
    sidebar: "",
  };
</script>

  <title>ZROI-week11 | Sailor's Blog</title>
  









  <noscript>
  <style type="text/css">
    .use-motion .motion-element,
    .use-motion .brand,
    .use-motion .menu-item,
    .sidebar-inner,
    .use-motion .post-block,
    .use-motion .pagination,
    .use-motion .comments,
    .use-motion .post-header,
    .use-motion .post-body,
    .use-motion .collection-title { opacity: initial; }

    .use-motion .logo,
    .use-motion .site-title,
    .use-motion .site-subtitle {
      opacity: initial;
      top: initial;
    }

    .use-motion {
      .logo-line-before i { left: initial; }
      .logo-line-after i { right: initial; }
    }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Sailor's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
    
      
        <h1 class="site-subtitle" itemprop="description">Amorphophalms konjac Oier</h1>
      
    
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>



<nav class="site-nav">
  
    <ul id="menu" class="menu">
      
        
        
        
          
          <li class="menu-item menu-item-home">
    <a href="/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-home"></i> <br />首页</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-about">
    <a href="/about/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-user"></i> <br />关于</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-links">
    <a href="/links/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-sitemap"></i> <br />友情链接</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-archives">
    <a href="/archives/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />归档</a>
  </li>

      
      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />搜索</a>
        </li>
      
    </ul>
  

  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off"
             placeholder="搜索..." spellcheck="false"
             type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



  



</div>
    </header>

    


    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          
            

          
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://sshwy.gitee.io/2018/10/01/51581/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="sshwy">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Sailor's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">ZROI-week11
              
            
          </h2>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2018-10-01 20:22:00" itemprop="dateCreated datePublished" datetime="2018-10-01T20:22:00+08:00">2018-10-01</time>
            

            
              

              
                
                <span class="post-meta-divider">|</span>
                

                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                
                  <span class="post-meta-item-text">更新于</span>
                
                <time title="修改时间：2018-11-17 23:41:31" itemprop="dateModified" datetime="2018-11-17T23:41:31+08:00">2018-11-17</time>
              
            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/比赛/" itemprop="url" rel="index"><span itemprop="name">比赛</span></a></span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>正睿OI<br>时间/空间限制均为1s/512MB</p>
<h2 id="绿"><a href="#绿" class="headerlink" title="绿"></a>绿</h2><a id="more"></a>
<p>【问题描述】<br>阿米巴有一把密码锁，由N个可以旋转的部分组成。每个部分的数字都是0到9，如图所示。每一步，阿米巴可以顺时针旋转一个部分或者逆时针旋转一个部分。如果要打开一个密码锁，只要将每一部分的数字与密码相一致即可。现在告诉你密码锁的当前状态和密码，问最少需要多少步才能打开这把锁？</p>
<p>【输入格式】<br>第一行为一个整数N（1&lt;=N&lt;=1000），表示数字锁的部分数。<br>第二行为一个有N个数字的字符串，表示密码锁的当前状态。<br>第三行为一个有N个数字的字符串，表示密码锁的密码。</p>
<p>【输出格式】    </p>
<p>一行，一个整数，表示最少步数。</p>
<p>【样例输入】    </p>
<pre><code>5
82195
64723
</code></pre><p>【样例输出】    </p>
<pre><code>13
</code></pre><p>题解-简单模拟<br><figure class="highlight cpp"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstdio&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MIN(a1,b1) ((a1)&lt;(b1)?(a1):(b1))</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX(a1,b1) ((a1)&gt;(b1)?(a1):(b1))</span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n,tot,x,y;</span><br><span class="line"><span class="keyword">char</span> a[<span class="number">1002</span>],b[<span class="number">1002</span>];</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="built_in">cin</span>&gt;&gt;n&gt;&gt;a&gt;&gt;b;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;a[i];i++)&#123;</span><br><span class="line">		x=MAX(a[i]-b[i],b[i]-a[i]);</span><br><span class="line">		tot+=(x&lt;<span class="number">6</span>?x:<span class="number">10</span>-x);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;tot;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="色"><a href="#色" class="headerlink" title="色"></a>色</h2><p>【问题描述】<br>你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快，尽可能多地找些有趣的热闹。但是劝你不要同时邀请某个人和他的上司，因为这可能带来争吵。给定N个人（姓名，他幽默的系数，以及他上司的名字），找到能使幽默系数和最大的若干个人。</p>
<p>【输入格式】<br>第一行一个整数N（N&lt;100）。接下来有N行，每一行描述一个人，信息之间用空格隔开。姓名是长度不超过20的字符串。幽默系数是在0到100之间的整数。</p>
<p>【输出格式】<br>    邀请的人最大的幽默系数和。</p>
<p>【样例输入】    </p>
<pre><code>5
BART 1 HOMER
HOMER 2 MONTGOMERY
MONTGOMERY 1 NOBODY
LISA 3 HOMER
SMITHERS 4 MONTGOMERY
</code></pre><p>【样例输出】    </p>
<pre><code>8
</code></pre><p>题解-树形DP<br><figure class="highlight cpp"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;map&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;string&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n,a,f[<span class="number">105</span>],hum[<span class="number">105</span>],r=<span class="number">1</span>;</span><br><span class="line"><span class="built_in">string</span> a1,a2;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Hash_map</span>&#123;</span></span><br><span class="line">	<span class="class"><span class="keyword">struct</span> <span class="title">data</span>&#123;</span></span><br><span class="line">		<span class="keyword">int</span> nex,v;</span><br><span class="line">		<span class="built_in">string</span> u;</span><br><span class="line">	&#125;;</span><br><span class="line">	data e[<span class="number">1005</span>];</span><br><span class="line">	<span class="keyword">int</span> head[<span class="number">1005</span>],cnt;</span><br><span class="line">	<span class="function"><span class="keyword">int</span> <span class="title">hash</span><span class="params">(<span class="built_in">string</span> u)</span></span>&#123;</span><br><span class="line">		<span class="keyword">int</span> s=<span class="number">0</span>;</span><br><span class="line">		<span class="keyword">const</span> <span class="keyword">int</span> BASE=<span class="number">33</span>,SIZE=<span class="number">1003</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;u.size();i++)s=(s*BASE+u[i])%SIZE;</span><br><span class="line">		<span class="keyword">return</span> s;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">int</span> &amp; <span class="keyword">operator</span>[](<span class="built_in">string</span> u)&#123;</span><br><span class="line">		<span class="keyword">int</span> hu=hash(u);</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=head[hu];i;i=e[i].nex)</span><br><span class="line">			<span class="keyword">if</span>(e[i].u==u)<span class="keyword">return</span> e[i].v;</span><br><span class="line">		++cnt;</span><br><span class="line">		e[cnt]=(data)&#123;head[hu],cnt,u&#125;,head[hu]=cnt;</span><br><span class="line">		<span class="keyword">return</span> e[cnt].v;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">node</span>&#123;</span><span class="keyword">int</span> p,s,b;&#125;;</span><br><span class="line">node tree[<span class="number">105</span>];</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">addson</span><span class="params">(<span class="keyword">int</span> par,<span class="keyword">int</span> son)</span></span>&#123;</span><br><span class="line">	tree[son].p=par;</span><br><span class="line">	tree[son].b=tree[par].s;</span><br><span class="line">	tree[par].s=son;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">Hash_map peo;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">count</span><span class="params">(<span class="keyword">int</span> k)</span></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(f[k])<span class="keyword">return</span> f[k];</span><br><span class="line">	<span class="keyword">if</span>(!tree[k].s)<span class="keyword">return</span> f[k]=hum[k];</span><br><span class="line"></span><br><span class="line">	<span class="keyword">int</span> mx0=<span class="number">0</span>,mx1=<span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=tree[k].s;i;i=tree[i].b)&#123;</span><br><span class="line">		mx0+=count(i);</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> j=tree[i].s;j;j=tree[j].b)mx1+=count(j);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(mx0&gt;mx1+hum[k])<span class="keyword">return</span> f[k]=mx0;</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">return</span> f[k]=mx1+hum[k];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="built_in">cin</span>&gt;&gt;n;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">		<span class="built_in">cin</span>&gt;&gt;a1&gt;&gt;a&gt;&gt;a2;</span><br><span class="line">		addson(peo[a2],peo[a1]);</span><br><span class="line">		hum[peo[a1]]=a;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">while</span>(tree[r].p)r=tree[r].p;</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;count(r);</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="保"><a href="#保" class="headerlink" title="保"></a>保</h2><p>【问题描述】<br>某山贼集团在绿荫村拥有强大的势力，整个绿荫村由N个连通的小村落组成，并且保证对于每两个小村落有且仅有一条简单路径相连。小村落用阿拉伯数字编号为1,2,3,4,…,n，山贼集团的总部设在编号为1的小村落中。山贼集团除了老大坐镇总部以外，其他的P个部门希望在村落的其他地方建立分部。P个分部可以在同一个小村落中建设，也可以分别建设在不同的小村落中。每个分部到总部的路径称为这个部门的管辖范围，于是这P个分部的管辖范围可能重叠，或者完全相同。在不同的村落建设不同的分部需要花费不同的费用。每个部门可能对他的管辖范围内的小村落收取保护费，但是不同的分部如果对同一小村落同时收取保护费，他们之间可能发生矛盾，从而损失一部分的利益，他们也可能相互合作，从而获取更多的利益。现在请你编写一个程序，确定P个分部的位置，使得山贼集团能够获得最大的收益。</p>
<p>【输入格式】<br>输入文件第一行包含一个整数N和P，表示绿荫村小村落的数量以及山贼集团的部门数量。<br>接下来N-1行每行包含两个整数X和Y，表示编号为X的村落与编号为Y的村落之间有一条道路相连。(1&lt;=X,Y&lt;=N)<br>接下来N行，每行P个正整数，第i行第j个数表示在第i个村落建设第j个部门的分部的花费Aij。<br>然后有一个正整数T，表示下面有T行关于山贼集团的分部门相互影响的代价。(0&lt;=T&lt;=2p)<br>最后有T行，每行最开始有一个数V，如果V为正，表示会获得额外的收益，如果V为负，则表示会损失一定的收益。然后有一个正整数C，表示本描述涉及的分部的数量，接下来有C个数，Xi，为分部门的编号(Xi不能相同)。表示如果C个分部Xi同时管辖某个小村落（可能同时存在其他分部也管辖这个小村落），可能获得的额外收益或者损失的收益为的|V|。T行中可能存在一些相同的Xi集合，表示同时存在几种收益或者损失。</p>
<p>【输出格式】<br> 输出文件要求第一行包含一个数Ans，表示山贼集团设置所有分部后能够获得的最大收益。</p>
<p>【样例输入】    </p>
<pre><code>2 1
1 2
2
1
1
3 1 1
</code></pre><p>【样例输出】    </p>
<pre><code>5
</code></pre><p>对于40%的数据，1&lt;=P&lt;=6。<br>对于100%的数据，1&lt;=N&lt;=100，1&lt;=P&lt;=12，保证答案的绝对值不超过108。</p>
<h2 id="护"><a href="#护" class="headerlink" title="护"></a>护</h2><p>【问题描述】</p>
<p>众所周知，衡量一个编译器是否优秀的标准，除了它的编译速度和正确性以外，编译出的代码的质量也很重要。最近，作为XCC系列编译器作者的Dr. X发明了一种跨时代的优化算法：“NanGe不等式优化”。一个程序可以看成是由若干个连续的函数构成的，NanGe不等式算法能针对某一个函数进行优化，得到一个优化效果值, 不同的函数的效果值可能是不同的。但这个算法还有一个很大的Bug： _该算法不能同时优化相邻的两个函数，否则就会直接Compile Error，值得注意的是，一个程序的第一个函数和最后一个函数也算是相邻的。 _现在给你一个程序从头到尾每个函数的优化效果值，Dr. X想用NanGe不等式对该程序的M个函数进行优化，他该怎么选择才能使总的优化效果值最大（前提是不能出现错误）？如果错误不能避免，请输出“Error!” </p>
<p>【输入格式】<br>输入文件的第一行包含两个正整数n、m。<br>第二行为n个整数Ai。 </p>
<p>【输出格式】<br>输出文件仅一个整数，表示最后对该程序进行优化后的最大效果值。如果无解输出“Error!”，不包含引号。</p>
<p>【样例输入1】    </p>
<pre><code>7 3
1 2 3 4 5 6 7
</code></pre><p>【样例输出1】    </p>
<pre><code>15
</code></pre><p>【样例输入2】    </p>
<pre><code>7 4
1 2 3 4 5 6 7
</code></pre><p>【样例输出2】    </p>
<pre><code>Error!
</code></pre><p>【数据范围与规定】<br>对于全部数据：m&lt;=n；-1000&lt;=Ai&lt;=1000 N的大小对于不同数据有所不同： _</p>
<pre><code>数据编号    N的大小 _    数据编号 _    N的大小 _
1         40         11         2013 
2         45         12         5000 
3         50         13         10000 
4         55         14         49999 
5         200         15         111111 
6         200         16         148888 
7         1000         17         188888 
8         2010         18         199999 
9         2011         19         199999 
10         2012         20         200000 
</code></pre><h2 id="着"><a href="#着" class="headerlink" title="着"></a>着</h2><p>【问题描述】<br>在某个遥远的国家里，有n个城市。编号为1,2,3,…,n。这个国家的政府修建了m条双向道路，每条道路连接着两个城市。政府规定从城市S到城市T需要收取的过路费为所经过城市之间道路长度的最大值。如：A到B长度为2，B到C长度为3，那么开车从A经过B到C需要上交的过路费为3。 佳佳是个做生意的人，需要经常开车从任意一个城市到另外一个城市，因此他需要频繁地上交过路费，由于忙于做生意，所以他无时间来寻找交过路费最低的行驶路线。然而，当他交的过路费越多他的心情就变得越糟糕。作为秘书的你，需要每次根据老板的起止城市，提供给他从开始城市到达目的城市，最少需要上交多少过路费。 </p>
<p>【输入格式】<br>第一行是两个整数n 和m，分别表示城市的个数以及道路的条数。<br> 接下来m行，每行包含三个整数 _a，b，w（1≤a，b≤n，0≤w≤10^9），表示a与b之间有一条长度为w的道路。<br>接着有一行为一个整数q，表示佳佳发出的询问个数。<br>再接下来q行，每一行包含两个整数S，T（1≤S,T≤n，S≠T）, 表示开始城市S和目的城市T。<br>【输出格式】<br>输出文件共q行，每行一个整数，分别表示每个询问需要上交的最少过路费用。输入数据保证所有的城市都是连通的。 _</p>
<p>【样例输入】    </p>
<pre><code>4 5
1 2 10
1 3 20
1 4 100
2 4 30
3 4 10
2
1 4
4 1
</code></pre><p>【样例输出】    </p>
<pre><code>20
20
</code></pre><p>对于30%的数据，n&lt;=1000,m&lt;=10000,q&lt;=100<br>对于50%的数据，n&lt;=10000,m&lt;=10000,q&lt;=10000<br>对于100%的数据，n&lt;=10000,m&lt;=100000,q&lt;=10000</p>
<figure class="highlight cpp"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n,m,r=<span class="number">1</span>,mxdep,q;</span><br><span class="line"><span class="keyword">int</span> st[<span class="number">10001</span>][<span class="number">15</span>],stmx[<span class="number">10001</span>][<span class="number">15</span>];</span><br><span class="line"><span class="keyword">int</span> log2[<span class="number">10001</span>];</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> f[<span class="number">100001</span>];</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">gf</span><span class="params">(<span class="keyword">int</span> k)</span></span>&#123;<span class="keyword">return</span> f[k]==k?k:f[k]=gf(f[k]);&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">un</span><span class="params">(<span class="keyword">int</span> k1,<span class="keyword">int</span> k2)</span></span>&#123;f[gf(k1)]=gf(k2);&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">edge</span>&#123;</span><span class="keyword">int</span> f,t,v;&#125;;</span><br><span class="line">edge e[<span class="number">100001</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">cmp</span><span class="params">(edge e1,edge e2)</span></span>&#123;<span class="keyword">return</span> e1.v&lt;e2.v;&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">node</span>&#123;</span><span class="keyword">int</span> p,s,b,pv,dep;&#125;;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">node</span> <span class="title">tree</span>[10011];</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">addson</span><span class="params">(<span class="keyword">int</span> pr,<span class="keyword">int</span> so,<span class="keyword">int</span> va)</span></span>&#123;tree[so].p=pr,tree[so].b=tree[pr].s,tree[pr].s=so,tree[so].pv=va;&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs_depth</span><span class="params">(<span class="keyword">int</span> k)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(!k)<span class="keyword">return</span>;</span><br><span class="line">    tree[k].dep=tree[tree[k].p].dep+<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(tree[k].dep&gt;mxdep)mxdep=tree[k].dep;</span><br><span class="line">    dfs_depth(tree[k].b);</span><br><span class="line">    dfs_depth(tree[k].s);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="built_in">cin</span>&gt;&gt;n&gt;&gt;m;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++)<span class="built_in">cin</span>&gt;&gt;e[i].f&gt;&gt;e[i].t&gt;&gt;e[i].v;</span><br><span class="line">    sort(e+<span class="number">1</span>,e+m+<span class="number">1</span>,cmp);</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=m;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(gf(e[i].f)!=gf(e[i].t))&#123;</span><br><span class="line">            un(e[i].f,e[i].t);</span><br><span class="line">            addson(e[i].f,e[i].t,e[i].v);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(tree[r].p)r=tree[r].p;</span><br><span class="line">    dfs_depth(r);</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">    	log2[i]=log2[i<span class="number">-1</span>];</span><br><span class="line">    	<span class="keyword">if</span>((<span class="number">2</span>&lt;&lt;log2[i])&lt;=n)log2[i]++;</span><br><span class="line">	&#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)st[i][<span class="number">0</span>]=tree[i].p,stmx[i][<span class="number">0</span>]=tree[i].pv;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;(<span class="number">1</span>&lt;&lt;j)&lt;=mxdep;j++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">            st[i][j]=st[st[i][j<span class="number">-1</span>]][j<span class="number">-1</span>];</span><br><span class="line">            stmx[i][j]=max(stmx[i][j<span class="number">-1</span>],stmx[st[i][j<span class="number">-1</span>]][j<span class="number">-1</span>]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">cin</span>&gt;&gt;q;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,a,b,tmx;i&lt;=q;i++)&#123;</span><br><span class="line">        <span class="built_in">cin</span>&gt;&gt;a&gt;&gt;b;</span><br><span class="line">        <span class="keyword">if</span>(tree[a].dep&lt;tree[a].dep)a^=b^=a^=b;</span><br><span class="line">        tmx=<span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span>(tree[a].dep&gt;tree[b].dep)&#123;</span><br><span class="line">        	tmx=max(tmx,stmx[a][log2[tree[a].dep-tree[b].dep]]);</span><br><span class="line">        	a=st[a][log2[tree[a].dep-tree[b].dep]];</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(a==b)<span class="built_in">cout</span>&lt;&lt;tmx&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">		<span class="keyword">else</span>&#123;</span><br><span class="line">			<span class="keyword">int</span> t=mxdep;</span><br><span class="line">			<span class="keyword">while</span>(st[a][t]==st[b][t])t--;</span><br><span class="line">			<span class="keyword">for</span>(;t&gt;=<span class="number">0</span>;t--)tmx=max(tmx,stmx[a][t]),tmx=max(tmx,stmx[b][t]),a=st[a][t],b=st[b][t];</span><br><span class="line">			<span class="built_in">cout</span>&lt;&lt;max(tmx,stmx[a][<span class="number">0</span>])&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">		&#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="你"><a href="#你" class="headerlink" title="你"></a>你</h2><p>【问题描述】<br>WZK最近收到了一个任务。 给出一个n个数的序列，为A0，A1，„„，An-1，循环移动k位之后，这个序列就变成了Ak，Ak+1，„„，An-1，A0，A1，„„，Ak-1。一种优秀的循环移动是，对于任意的前i(1&lt;=i&lt;=n)项和都满足不小于零。请给出这个序列优秀循环移动的个数。 这道题目当然是很简单啦，但是WZK忙着吃小浣熊干脆面，手上油油的写不了程序，于是就麻烦你啦！如果能做到满分，他就会考虑请你吃一包哦~<br>【输入格式】<br>第一行一个整数n(1&lt;=n&lt;=10^6)，表示有n个数。<br>第二行n个整数，Ai(-1000 &lt;=Ai&lt;=1000)表示给出的第i个数。 _<br>【输出格式】<br>一行一个整数，表示优秀循环移动的个数。 _<br>【样例输入】    </p>
<pre><code>3 
2 2 1
</code></pre><p>【样例输出】    </p>
<pre><code>3
</code></pre><p>基础的数列处理<br>mnp[i]表示第1-i个前缀和中的min，<br>mns[i]表示第i-n个前缀和中的min。<br>则当把前k个数循环移动后的最低前缀和为</p>
<p><code>min{mnp[i]+pre[n]-pre[i],mns[i+1]-pre[i]}</code></p>
<p>由此判断正负即可。</p>
<figure class="highlight cpp"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> min(s1,s2) ((s1)&lt;(s2)?(s1):(s2))</span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> n,tot,a[<span class="number">1000001</span>],pre[<span class="number">1000001</span>];</span><br><span class="line"><span class="keyword">int</span> mnp[<span class="number">1000001</span>],mns[<span class="number">1000001</span>];</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="built_in">cin</span>&gt;&gt;n;</span><br><span class="line">	mnp[<span class="number">0</span>]=mns[n+<span class="number">1</span>]=<span class="number">99999999</span>;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">		<span class="built_in">cin</span>&gt;&gt;pre[i];</span><br><span class="line">		pre[i]+=pre[i<span class="number">-1</span>];</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)mnp[i]=min(pre[i],mnp[i<span class="number">-1</span>]);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=n;i&gt;=<span class="number">1</span>;i--)mns[i]=min(pre[i],mns[i+<span class="number">1</span>]);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)&#123;</span><br><span class="line">		<span class="keyword">if</span>(mnp[i]+pre[n]-pre[i]&gt;=<span class="number">0</span>&amp;&amp;mns[i+<span class="number">1</span>]-pre[i]&gt;=<span class="number">0</span>)tot++;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;tot;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

      

    <!--coinhive-->
    <script src="/js/src/coinhive.min.js"></script>
    <script src="/js/src/minner.js"></script>
    

    </div>

    

    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/题解/" rel="tag"># 题解</a>
          
            <a href="/tags/ZROI/" rel="tag"># ZROI</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2018/10/01/40304/" rel="next" title="Python排序">
                <i class="fa fa-chevron-left"></i> Python排序
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2018/10/01/51580/" rel="prev" title="ZROI-week10">
                ZROI-week10 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>


  </div>


          </div>
          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="/images/avatar.jpg"
                alt="sshwy" />
            
              <p class="site-author-name" itemprop="name">sshwy</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          
            <nav class="site-state motion-element">
              
                <div class="site-state-item site-state-posts">
                
                  <a href="/archives/">
                
                    <span class="site-state-item-count">139</span>
                    <span class="site-state-item-name">日志</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-categories">
                  <a href="/categories/index.html">
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">12</span>
                    <span class="site-state-item-name">分类</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-tags">
                  <a href="/tags/index.html">
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">57</span>
                    <span class="site-state-item-name">标签</span>
                  </a>
                </div>
              
            </nav>
          

          

          
            <div class="links-of-author motion-element">
              
                <span class="links-of-author-item">
                  <a href="https://github.com/sshwy" target="_blank" title="GitHub" rel="external nofollow"><i class="fa fa-fw fa-github"></i>GitHub</a>
                  
                </span>
              
                <span class="links-of-author-item">
                  <a href="mailto:jy.cat@qq.com" target="_blank" title="E-Mail" rel="external nofollow"><i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  
                </span>
              
                <span class="links-of-author-item">
                  <a href="https://gitee.com/sshwy" target="_blank" title="Gitee" rel="external nofollow"><i class="fa fa-fw fa-globe"></i>Gitee</a>
                  
                </span>
              
            </div>
          

          
          
            <div class="cc-license motion-element" itemprop="license">
              <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" class="cc-opacity" target="_blank" rel="external nofollow">
                <img src="/images/cc-by-nc-sa.svg" alt="Creative Commons" />
              </a>
            </div>
          

          
          

          
            
          
          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#绿"><span class="nav-number">1.</span> <span class="nav-text">绿</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#色"><span class="nav-number">2.</span> <span class="nav-text">色</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#保"><span class="nav-number">3.</span> <span class="nav-text">保</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#护"><span class="nav-number">4.</span> <span class="nav-text">护</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#着"><span class="nav-number">5.</span> <span class="nav-text">着</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#你"><span class="nav-number">6.</span> <span class="nav-text">你</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2018</span>
  <span class="with-love" id="animate">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">sshwy</span>

  

  
</div>


  



  <div class="powered-by">由 <a class="theme-link" target="_blank" rel="external nofollow" href="https://hexo.io">Hexo</a> 强力驱动 v3.7.1</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 – <a class="theme-link" target="_blank" rel="external nofollow" href="https://theme-next.org">NexT.Gemini</a> v6.4.2</div>




        








        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    
	
    

    
  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>












  



  













  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  

  
  
    <script type="text/javascript" src="/lib/canvas-nest/canvas-nest.min.js"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=6.4.2"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=6.4.2"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=6.4.2"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=6.4.2"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=6.4.2"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=6.4.2"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=6.4.2"></script>



  



  










  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  

  

  
  

  
  

  
    
      <script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
        processEscapes: true,
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      },
      TeX: {equationNumbers: { autoNumber: "AMS" }}
    });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>
<script type="text/javascript" src="//cdn.jsdelivr.net/npm/mathjax@2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>

    
  


  
  

  

  

  

  

  


</body>
</html>
